`
https://leetcode.cn/problems/cheapest-flights-within-k-stops/
`

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
var findCheapestPrice = function (n, flights, src, dst, k) {
  k++
  const memo = new Array(n).fill().map(() => new Array(k + 1).fill(-1))
  // 构建入度 to -> [from, price]
  const indegree = new Map()
  for (const f of flights) {
    const from = f[0], to = f[1], price = f[2]
    if (!indegree.has(to)) {
      indegree.set(to, [])
    }
    indegree.get(to).push([from, price])
  }

  // 定义：从 src 出发，k 步之内到达 s 的最小成本
  function dp(s, k) {
    // 到终点了，不需要再走
    if (s === src) {
      return 0
    }

    // 步数走完了还没到，说明没解
    if (k === 0) {
      return -1
    }

    // 如果已经计算过
    if (memo[s][k] !== -1) {
      return memo[s][k]
    }

    let res = Infinity
    if (indegree.has(s)) {
      // 从 s 出发，遍历所有的入度
      // 这里的入度是反向的，表示从 s 到 from 的边
      for (const v of indegree.get(s)) {
        const from = v[0];
        const price = v[1];
        // 从 from 出发，k - 1 步到达 s 的最小成本
        const subProblem = dp(from, k - 1);
        // 如果 subProblem 不等于 -1，说明可以到达
        if (subProblem !== -1) {
          // 那么就更新 res
          res = Math.min(res, subProblem + price);
        }
      }
    }

    memo[s][k] = res === Infinity ? -1 : res
    return memo[s][k]
  }

  return dp(dst, k)
};